#include <iostream>
#include <string>
#include <algorithm>
#include <time.h>
#include <vector>
#include <map>
#include <unordered_map>

using namespace std;

//二叉树的伪回文路径
//https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    unordered_map<int, int> map;
    int ret = 0;

    int pseudoPalindromicPaths(TreeNode* root)
    {
        map[root->val]++;
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root)
    {
        if (!root->left && !root->right)
        {
            //找到根节点,判断hash表内的值是否可以构成回文
            int sum_1 = 0; //奇数个
            for (auto& e : map)
            {
                if (e.second % 2 != 0) sum_1++;
            }

            if (sum_1 > 1) return;
            ret++;
            return;
        }


        if (root->left)
        {
            int val = root->left->val;
            map[val]++;
            dfs(root->left);
            map[val]--;
            if (map.count(val) == 0) map.erase(val);
        }

        if (root->right)
        {
            int val = root->right->val;
            map[val]++;
            dfs(root->right);
            map[val]--;
            if (map.count(val) == 0) map.erase(val);
        }

        return;
    }
};

int main()
{
    unordered_map<int, int> map;
    map[1]++;
    cout << map[1] << endl;
	return 0;
}